package visualizer.client.algorithms.rbBst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.ArrayList;
import java.util.List;

import static visualizer.client.utils.VisualizerUtils.DEFAULT_OUTER_COLOR;

/**
 * User: DDovzhenko
 * Date: 07.01.14
 * Time: 18:25
 */
public class RBBSTSearchingAlgorithm implements Algorithm {
    public static final String BLUE = "blue";
    private BinaryTree tree;
    private List<AlgoResult> results = new ArrayList<AlgoResult>();

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return results.get(step);
    }

    @Override
    public int getStepsCount(BinaryTree binaryTree, int inputValue) {
        results.clear();
        results.add(new AlgoResult(binaryTree.copyTree(true), "Поиск узла с ключом " + inputValue));
        tree = binaryTree.copyTree(true);
        boolean isFound = false;
        if (tree.getRoot() != null) {
            isFound = search(tree.getRoot(), inputValue);
        } else {
            results.add(new AlgoResult(tree.copyTree(true), "Дерево пусто, узел не найден"));
        }
        if (isFound) {
            results.add(new AlgoResult(tree.copyTree(true), "Узел найден"));
        } else {
            results.add(new AlgoResult(tree.copyTree(true), "Узел не найден"));
        }
        return results.size();
    }

    private boolean search(BNode node, int key) {
        node.setOuterColor(BLUE);
        if (key < node.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " < " + node.getValue() + ", обрабатываем левое поддерево"));
            if (node.getLeftBNode() != null) {
                node.setOuterColor(DEFAULT_OUTER_COLOR);
                return search(node.getLeftBNode(), key);
            } else {
                node.setOuterColor(BLUE);
                results.add(new AlgoResult(tree.copyTree(true), "Здесь нет узла, узел не найден"));
                node.setOuterColor(DEFAULT_OUTER_COLOR);
                return false;
            }
        } else if (key > node.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " > " + node.getValue() + ", обрабатываем правое поддерево"));
            if (node.getRightBNode() != null) {
                node.setOuterColor(DEFAULT_OUTER_COLOR);
                return search(node.getRightBNode(), key);
            } else {
                node.setOuterColor(BLUE);
                results.add(new AlgoResult(tree.copyTree(true), "Здесь нет узла, узел не найден"));
                node.setOuterColor(DEFAULT_OUTER_COLOR);
                return false;
            }
        } else {
            node.setOuterColor(BLUE);
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: " + key + " = " + node.getValue() + ", узел найден"));
            node.setOuterColor(DEFAULT_OUTER_COLOR);
            return true;
        }
    }
}
